package violencerecursion;

/**
 * @author tongchen
 * @create 2023-03-27 21:31
 */
public class DpNumConvert {
    public int dpConvert(String s){
        //将s转化为数组
        char[] chars = s.toCharArray();
        //选择从后往前遍历从最后一个往前遍历，观察最后能有多少各种组合结果：初始的组合结果为1
        //创建动态数组
        int[]N=new int[chars.length+1];
        N[chars.length]=1;
        for(int i=chars.length-1;i>=0;--i){
            if(chars[i]==1){
                N[i]=N[i+1];
                if(i+1<N.length-1){
                    N[i]+=N[i+2];
                }
            }
            else if(chars[i]==2){
                N[i]=N[i+1];
                if((i+1<N.length-1)&&chars[i+1]>='0'&&chars[i+1]<='5'){
                    N[i]+=N[i+2];
                }
            }
            else{
                N[i]=N[i+1];
            }
        }
        return N[0];
    }
}
